串′ababaaababaa′的next数组（求next数组思路与实例）

刚刚开始遇到这个问题说实话完全懵逼，然后简单搜了下，还是理解的模棱两可。最后看了几篇博客，现在才算是真正的理解了。

首先在将例子之前先说说这个next数组求解的思路：

第一位的next的值是0，第二位的next的值为1，后面求解每一位的next的值时。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，如果不等，向前继续寻找next值对应的内容与前一位进行比较（向前继续寻找next值对应的内容与next值对应的内容的next前一位进行比较），直到找到某个位上的内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。所以中心思想则是递进查看前一位的next对应的是否和前一位相同。找到相同的则在找到的基础上加1。

求串′ababaaababaa′的next数组

1、前两位：next数组前两位规定是0，1 即前两位ab对应的next数组为01，则：

2、接下来看第三位，按照next数组求解方法。第三位a的前一位为第二位的b，b的next值为1对应内容为a，b与a不同，向前继续寻找next值对应的内容来与前一位进行比较。因为找到第一位都没有找到与前一位相等的内容，所以第三位a的next值为1，则：

3、接下来看第四位b，b的前一位a的next值1对应内容为a，相同，所以该位b的next值就是前一位a的next值加上1，即为2

4、接下来看第五位a，a的前一位b的next值2对应内容为b，相等，所以该位a的next值就是前一位b的next值加上1，即为3

5、接下来看第六位a，a的前一位a的next值3对应内容为a，相等，所以该位a的next值就是前一位a的next值加上1，即为4

6、接下来看第七位a，a的前一位a的next值4对应内容为b，不相等，向前继续寻找next值对应的内容来与前一位进行比较，b的next值2对应的内容为b，依旧不相等，继续向前寻找，第二位b的next值1对应内容为a，相等。因为是在第二位b处实现的相等，所以第七位a的next值为第二位b的next值上加1，即为2

7、接下来看第八位，同样道理，得出b的next值为2

8、接下来看第九位，前一位b的next值2对应内容为b，相等，所以此处next值为3

9、第十位同理可得，为4

10、第十一位a的前一位b的next值4对应内容为b，相等，所以此处next值为5

11、最后，第十二位同理可以得到next值位6